#include <stdio.h>
#include <malloc.h>

//将题目1.3要求定义为子函数，子函数中不能调用第三章资料中给的函数，可以调用自己定义的函数。 
//
//main()函数中可以调用第三章资料中给的函数。
//
//在main（）函数中调用子函数进行测试。
//请设计一个队列，要求满足：
// ①初始时队列为空；
// ②入队时，允许增加队列占用空间；
// ③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
//④入队操作和出队操作的时间复杂度始终保持为O(1)。请回答下列问题：
//
//（1）该队列是应选择链式存储结构，还是应选择顺序存储结构？
//  链式存储结构
//（2）画出队列的初始状态，并给出判断队空和队满的条件。
//
//（3）试编写算法分别实现队列初始化、入队列和出队列操作。

typedef int ElemType;
typedef struct DataNode{
	ElemType data;
	struct DataNode *next;
}DataNode;

typedef struct{
	DataNode *front;//头指针
	DataNode *rear;//尾指针
} ListQueue;

//初始化
void InitQueue(ListQueue* &q)
{
	q = (ListQueue*)malloc(sizeof(ListQueue));
	q->front = (DataNode*)malloc(sizeof(DataNode));
	q->front->next = q->front;
	q->rear = q->front;
}

//入队
void EnQueue(ListQueue* &q,ElemType e)
{
	if(q->rear->next==q->front)//队满
	{
		DataNode* s = (DataNode*)malloc(sizeof(DataNode));
		s->next = q->rear->next;
		q->rear->next = s;
		q->rear->data = e;
	}
	else{
		q->rear->data = e;
	}
	q->rear = q->rear->next;
}


//出队
bool DeQueue(ListQueue*& q,ElemType&e)
{
	if(q->front==q->rear) return false;//队空
	e = q->front->data;
	q->front = q->front->next;
	
	return true;
}


void print(ListQueue* q)
{
	DataNode* p = q->front;
	while(p!=q->rear)
	{
		printf("%d ",p->data);
		p = p->next;
	}
}
void DestroyQueue(ListQueue *&q)
{
	DataNode *p=q->front,*r;//p指向队头数据结点
	if (p!=q->rear)			//释放数据结点占用空间
	{	r=p->next;
		while (r!=q->rear)
		{	free(p);
			p=r;r=p->next;
		}
		free(r);
	}
	free(p);
	free(q);				//释放链队结点占用空间
}


int main()
{
	ListQueue* q;
	InitQueue(q);
	EnQueue(q,20);
	EnQueue(q,10);
	print(q);
	
	int e = 0;
	DeQueue(q,e);
	printf("\n");
	print(q);
	
	
	DestroyQueue(q);
	
	return 0;
}
